{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### 57. Insert Interval\n",
    "Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).\n",
    "\n",
    "You may assume that the intervals were initially sorted according to their start times.\n",
    "\n",
    "    Example 1:\n",
    "        Input: intervals = [[1,3],[6,9]], newInterval = [2,5]\n",
    "        Output: [[1,5],[6,9]]\n",
    "    Example 2:\n",
    "        Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]\n",
    "        Output: [[1,2],[3,10],[12,16]]\n",
    "        Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].\n",
    "> NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param intervals:\n",
    "        :param newInterval:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        merge = []\n",
    "        is_added = -1\n",
    "        for element in intervals:\n",
    "            if not merge:\n",
    "                if element[1] < newInterval[0]:\n",
    "                    merge.append(element)\n",
    "                elif element[0] > newInterval[1]:\n",
    "                    merge.append(newInterval)\n",
    "                    merge.append(element)\n",
    "                    is_added = 1\n",
    "                elif element[0] <= newInterval[0] and element[1] >= newInterval[1]:\n",
    "                    merge.append(element)\n",
    "                    is_added = 1\n",
    "                elif element[0] >= newInterval[0] and element[1] <= newInterval[1]:\n",
    "                    merge.append(newInterval)\n",
    "                    is_added = 0\n",
    "                elif element[0] <= newInterval[0] and element[1] <= newInterval[1]:\n",
    "                    merge.append([element[0], newInterval[1]])\n",
    "                    is_added = 0\n",
    "                else:\n",
    "                    merge.append([newInterval[0], element[1]])\n",
    "                    is_added = 1\n",
    "            else:\n",
    "                if is_added == 1:\n",
    "                    merge.append(element)\n",
    "                elif is_added == 0:\n",
    "                    if element[0] > merge[-1][1]:\n",
    "                        merge.append(element)\n",
    "                        is_added = 1\n",
    "                    elif element[1] > merge[-1][1]:\n",
    "                        merge[-1][1] = element[1]\n",
    "                        is_added = 1\n",
    "                    else:\n",
    "                        pass\n",
    "                else:\n",
    "                    if element[1] < newInterval[0]:\n",
    "                        merge.append(element)\n",
    "                    elif element[0] > newInterval[1]:\n",
    "                        merge.append(newInterval)\n",
    "                        merge.append(element)\n",
    "                        is_added = 1\n",
    "                    elif element[0] <= newInterval[0] and element[1] >= newInterval[1]:\n",
    "                        merge.append(element)\n",
    "                        is_added = 1\n",
    "                    elif element[0] >= newInterval[0] and element[1] <= newInterval[1]:\n",
    "                        merge.append(newInterval)\n",
    "                        is_added = 0\n",
    "                    elif element[0] <= newInterval[0] and element[1] <= newInterval[1]:\n",
    "                        merge.append([element[0], newInterval[1]])\n",
    "                        is_added = 0\n",
    "                    else:\n",
    "                        merge.append([newInterval[0], element[1]])\n",
    "                        is_added = 1\n",
    "        if is_added == -1:\n",
    "            merge.append(newInterval)\n",
    "        return merge"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "source": [
    "intervals = [[1,3],[6,9]]\n",
    "newInterval = [2,5]\n",
    "S = Solution()\n",
    "print(S.insert(intervals, newInterval))\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "execution_count": 2,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 5], [6, 9]]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2], [3, 10], [12, 16]]\n"
     ]
    }
   ],
   "source": [
    "intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\n",
    "newInterval = [4,8]\n",
    "S = Solution()\n",
    "print(S.insert(intervals, newInterval))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[5, 7]]\n"
     ]
    }
   ],
   "source": [
    "intervals = []\n",
    "newInterval = [5,7]\n",
    "S = Solution()\n",
    "print(S.insert(intervals, newInterval))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 7]]\n"
     ]
    }
   ],
   "source": [
    "intervals = [[1,5]]\n",
    "newInterval = [1,7]\n",
    "S = Solution()\n",
    "print(S.insert(intervals, newInterval))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 5], [6, 8]]\n"
     ]
    }
   ],
   "source": [
    "intervals = [[1,5]]\n",
    "newInterval = [6,8]\n",
    "S = Solution()\n",
    "print(S.insert(intervals, newInterval))\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}